package recusive;

import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;

import java.util.List;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;

/**
 * @author luo
 * @description
 * @since 2022/7/22 20:00
 */
public class LongestSubstring {

    private String str;
    private int lestCount;

    private int maxRepeatCount;

    private String maxRepeatString = "";

    @Test
    @DisplayName("至少有k个重复字符的最长子串")
    public void test() {
        longestSubstring("ababbc", 2);
        System.out.println("最长子串：" + maxRepeatString);
        System.out.println("最长长度：" + maxRepeatCount);
    }


    /**
     * 给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串，
     * 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。
     *
     * @param s
     * @param k
     * @return
     */
    public int longestSubstring(String s, int k) {
        str = s;
        lestCount = k;
        find(0, str.length() - 1);
        return maxRepeatString.length();
    }

    private StringBuilder find(int leftIndex, int rightIndex) {
        if (leftIndex == rightIndex) {
            return new StringBuilder(str.substring(leftIndex, leftIndex + 1));
        }

        int middleIndex = (leftIndex + rightIndex) / 2;
        StringBuilder leftStr = find(leftIndex, middleIndex);
        StringBuilder rightStr = find(middleIndex + 1, rightIndex);
        StringBuilder appendResult = new StringBuilder(leftStr).append(rightStr);

        if ((rightIndex - leftIndex - 1) % lestCount == 0) {
            Map<Integer, List<Integer>> collect = appendResult.toString().chars().mapToObj(Integer::new).collect(Collectors.groupingBy(Function.identity()));
            if (collect.values().stream().allMatch(count -> count.size() == lestCount)) {
                maxRepeatString = appendResult.toString();
                maxRepeatCount = maxRepeatString.length();
            }
        }

        return appendResult;
    }

    static class StrUnit{
        StringBuilder stringBuilder;

    }

}
